Introduction

RSA is one of the most important algorithms in modern cryptography.
It protects online shopping, banking, messaging, and almost every secure connection on the internet.

This article explains:

• Why RSA was invented
• The simple number‑theory ideas behind it
• How keys are created
• How encryption and decryption work
• Why RSA is secure in practice

Why We Need Secure Communication

When you send information online, it often travels through:

• Public networks
• Shared servers
• Untrusted intermediaries

Without protection, anyone could:

• Read your messages
• Steal passwords
• Alter data
• Pretend to be someone else

Cryptography solves these problems by:

• Scrambling information
• Requiring special keys to read it
• Ensuring messages cannot be forged

RSA is one of the most famous tools for doing this.

A Gentle Overview of Public‑Key Cryptography

Traditional (symmetric) cryptography:

• Uses one shared secret key
• Both sides must know it
• Hard to distribute keys safely

Public‑key cryptography:

• Each person has two keys
  • A public key (shared openly)
  • A private key (kept secret)
• Anyone can encrypt using the public key
• Only the private key can decrypt

Key idea:

• The public key does not reveal the private key
• This allows secure communication with strangers

The Big Idea Behind RSA

RSA is built on a simple but powerful concept:

• Some mathematical operations are easy to do
• But very hard to undo without special information

In RSA:

• Multiplying two large primes is easy
• Factoring the product is extremely hard

RSA uses this asymmetry to create:

• A public key (easy to compute)
• A private key (easy to compute if you know the primes)
• A system that is hard to break without those primes

Prime Numbers and Factorisation: The Hidden Difficulty

Prime numbers are the backbone of RSA.

Important facts:

• A number like $n = pq$ (product of two primes) is easy to compute
• But given $n$, finding $p$ and $q$ is extremely difficult when they are large

Why this matters:

• RSA keys use primes hundreds of digits long
• No known efficient method exists to factor such numbers
• This difficulty is what keeps RSA secure

Even powerful computers struggle with factorisation at RSA sizes.

Modular Arithmetic for RSA (Light Version)

RSA uses modular arithmetic, but only a few ideas are needed:

Key concepts

• $a \bmod n$ means the remainder when $a$ is divided by $n$
• Modular multiplication works like normal multiplication, then reduce
• Modular exponentiation means repeated multiplication with reduction

Why it’s useful

• Keeps numbers manageable
• Allows reversible operations
• Makes encryption and decryption efficient

Two key operations in RSA

• Encryption: $$c \equiv m^e \pmod{n}$$
• Decryption: $$m \equiv c^d \pmod{n}$$

Where:

• $m$ = message
• $c$ = ciphertext
• $e$ = public exponent
• $d$ = private exponent
• $n$ = product of two primes

How RSA Keys Are Created

Key generation steps (simplified):

1. Choose two large primes
   • Call them $p$ and $q$
2. Multiply them
   • $n = pq$
   • This becomes part of the public key
3. Compute
   • $\varphi(n) = (p-1)(q-1)$
   • $\varphi$ is a Greek letter pronounced "Phi"
   • $\varphi(n)$ is called "Euler’s totient"
   • It counts how many numbers are “compatible” with $n$
4. Choose a public exponent $e$
   • Usually a small number like $65537$
   • Must be coprime with $\varphi(n)$
5. Compute the private exponent $d$
   • $d$ is the number satisfying $$ed \equiv 1 \pmod{\varphi(n)}$$
   • This means $d$ “undoes” the effect of $e$
6. Publish
   • Public key: $(n, e)$
   • Private key: $(n, d)$

Only $p$ and $q$ must remain secret.

How Encryption and Decryption Work

Encryption

To send a message $m$:

• Compute $$c \equiv m^e \pmod{n}$$
• Send $c$

Anyone can do this using the public key.

Decryption

To recover the message:

• Compute $$m \equiv c^d \pmod{n}$$

Only the private key holder knows $d$, so only they can decrypt.

Why it works

The exponents $e$ and $d$ are chosen so that: $$m^{ed} \equiv m \pmod{n}$$ This is a deep result from number theory, but the intuition is:

• $e$ scrambles
• $d$ unscrambles

Why RSA Is Hard to Break

Breaking RSA means:

• Recovering $d$ from $(n, e)$
• Or factoring $n$ into $p$ and $q$

Both are believed to be extremely difficult.

Reasons:

• No known fast algorithm for factoring large numbers
• RSA keys are hundreds or thousands of bits long
• Even supercomputers take impractically long to factor them

Security relies on:

• Prime numbers
• Factorisation difficulty
• Modular arithmetic properties

Real‑World Uses of RSA Today

RSA is everywhere:

• Secure websites (HTTPS)
• Online banking
• Email encryption
• Digital signatures
• Software updates
• Secure messaging
• Virtual private networks (VPNs)

RSA often works alongside other algorithms to create secure systems.

Limitations of RSA and Modern Alternatives

RSA is powerful but not perfect.

Limitations

• Slow for large amounts of data
• Requires large keys for strong security
• Vulnerable to future quantum computers

Modern alternatives

• Elliptic Curve Cryptography (ECC)
  • Smaller keys
  • Faster operations
• Post‑quantum cryptography
  • Designed to resist quantum attacks
• Hybrid systems
  • RSA for key exchange
  • Faster symmetric ciphers for data

Exercises

1. Build a Tiny RSA Key

   Choose two small primes:

   • Pick any two primes between 5 and 20
   • Compute
   • $n = pq$
   • $\varphi(n) = (p-1)(q-1)$

   Write down your chosen primes and the results.

   Solution

   Answers vary; here’s one concrete example.

   • Choose primes: $p = 7$, $q = 11$
   • Compute $n$: $$n = pq = 7 \cdot 11 = 77$$
   • Compute $\varphi(n)$: $$\varphi(n) = (p-1)(q-1) = 6 \cdot 10 = 60$$

   Any correct pair of primes and correct $n,\ \varphi(n)$ is fine.

2. Choose a Valid Public Exponent

   Using your $\varphi(n)$ from Exercise 1:

   • List all numbers between 2 and $\varphi(n)$
   • Circle the ones that are coprime to $\varphi(n)$
   • Choose one to be your public exponent $e$

   (You can check coprimality by seeing if they share any common factors.)

   Solution

   We need to find all integers $e$ such that:

   • $2 \le e < \varphi(n)$
   • $\gcd(e, 60) = 1$

   Since $$60 = 2^2 \cdot 3 \cdot 5,$$ a number is coprime with 60 if and only if it is divisible by none of 2, 3, or 5.

   So we list all numbers from 2 to 59 and remove those divisible by 2, 3, or 5.

   All valid public exponents $e$ (coprime with 60)

   $$7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 49,\ 53,\ 59$$

   Notes

   • 49 is valid, because $\gcd(49, 60) = 1$.
   • These are exactly the integers less than 60 that avoid the prime factors 2, 3, and 5.

3. Compute Your Private Key

   Find $d$ such that: $$ed \equiv 1 \pmod{\varphi(n)}$$ Tasks:

   • Try small values of $d$
   • Multiply $e \cdot d$ each time
   • Stop when the product is one more than a multiple of $\varphi(n)$

   This $d$ is your private key.

   Solution

   We want $d$ such that: $$ed \equiv 1 \pmod{\varphi(n)}$$ With $e = 7$ and $\varphi(n) = 60$:

   • Try multiples of $7$:
     $7 \cdot 43 = 301$
   • Check modulo $60$: $$301 \equiv 1 \pmod{60}$$

   So:

   • $d = 43$

4. Encrypt a Message You Choose

   Pick a small message number $m$ (for example, your favourite number between 1 and $n-1$).

   Compute: $$c \equiv m^e \pmod{n}$$ Write down:

   • Your message $m$
   • Your ciphertext $c$

   Solution

   Example:

   • $m = 5$, $e = 7$, $n = 77$

   Compute: $$c \equiv 5^7 \pmod{77}$$ Step by step:

   • $5^2 = 25$
   • $5^3 = 125 \equiv 48 \pmod{77}$
   • $5^4 = 48 \cdot 5 = 240 \equiv 9 \pmod{77}$
   • $5^7 = 5^4 \cdot 5^3 = 9 \cdot 48 = 432 \equiv 47 \pmod{77}$

   So:

   • Ciphertext $c = 47$

5. Decrypt the Message

   Using your private key $d$, compute: $$m \equiv c^d \pmod{n}$$ Check that you recover the original message.

   (Hint: break the exponent into smaller powers, e.g. square‑and‑multiply.)

   Solution

   • Modulus: $n = 77$
   • Public exponent: $e = 7$
   • Private exponent: $d = 43$
   • Ciphertext: $c = 47$

   We want to recover the original message $m$ by computing $$m \equiv c^d \pmod{n} = 47^{43} \pmod{77}.$$ We’ll use repeated squaring to keep numbers small.

   Step 1: Compute powers of $47$ modulo $77$

   • $a = 47$
   • $a^2$ $$47^2 = 2209$$ So $$a^2 \equiv 53 \pmod{77}.$$
   • $a^4$ $$a^4 = (a^2)^2 \equiv 53^2 = 2809$$ So $$a^4 \equiv 37 \pmod{77}.$$
   • $a^8$ $$a^8 = (a^4)^2 \equiv 37^2 = 1369$$ So $$a^8 \equiv 60 \pmod{77}.$$
   • $a^{16}$ $$a^{16} = (a^8)^2 \equiv 60^2 = 3600$$ So $$a^{16} \equiv 58 \pmod{77}.$$
   • $a^{32}$ $$a^{32} = (a^{16})^2 \equiv 58^2 = 3364$$ So $$a^{32} \equiv 53 \pmod{77}.$$

   Step 2: Express the exponent 43 in binary form

   We write: $$43 = 32 + 8 + 2 + 1$$ So: $$47^{43} = 47^{32} \cdot 47^8 \cdot 47^2 \cdot 47^1$$ Using our earlier results:

   • $47^{32} \equiv 53$
   • $47^8 \equiv 60$
   • $47^2 \equiv 53$
   • $47^1 \equiv 47$

   Step 3: Multiply these together modulo 77

   First: $$53 \cdot 60 = 3180$$ So: $$53 \cdot 60 \equiv 23 \pmod{77}.$$ Next: $$23 \cdot 53 = 1219$$ So: $$23 \cdot 53 \equiv 64 \pmod{77}.$$ Finally: $$64 \cdot 47 = 3008$$ So: $$64 \cdot 47 \equiv 5 \pmod{77}.$$ Therefore: $$47^{43} \equiv 5 \pmod{77}.$$ So the decrypted message is:

   • $m = 5$

   This matches the original message we encrypted earlier, showing that the RSA decryption step works correctly in this example.

6. Break a Tiny RSA System

   Suppose someone’s public key is:

   • $n = 77$
   • $e = 5$

   Tasks:

   1. Factor $77$
   2. Compute $\varphi(77)$
   3. Find the private key $d$
   4. Decrypt the ciphertext $c = 23$

   This simulates breaking RSA when $n$ is too small.

7. Compare Two RSA Keys

   Generate two tiny RSA keys using different primes.

   For each:

   • Compute $n$
   • Compute $\varphi(n)$
   • Choose $e$
   • Compute $d$

   Then answer:

   • Which key has the larger $n$?
   • Which one would be harder to break?
   • Why?

   Solution

   Key A

   • Primes:
     • $p_1 = 7$, $q_1 = 11$
   • Modulus:
     • $n_1 = p_1 q_1 = 7 \cdot 11 = 77$
   • Euler’s totient:
     • $\varphi(n_1) = (7-1)(11-1) = 6 \cdot 10 = 60$
   • Public exponent (chosen coprime with 60):
     • $e_1 = 7$
   • Private exponent:
     • Solve $7d_1 \equiv 1 \pmod{60}$
     • $7 \cdot 43 = 301 \equiv 1 \pmod{60}$
     • So $d_1 = 43$

   So Key A is:

   • Public: $(n_1, e_1) = (77, 7)$
   • Private: $(n_1, d_1) = (77, 43)$

   Key B

   • Primes:
     • $p_2 = 13$, $q_2 = 17$
   • Modulus:
     • $n_2 = p_2 q_2 = 13 \cdot 17 = 221$
   • Euler’s totient:
     • $\varphi(n_2) = (13-1)(17-1) = 12 \cdot 16 = 192$
   • Public exponent (coprime with 192):
     • Take $e_2 = 5$ (since $\gcd(5,192) = 1$)
   • Private exponent:
     • Solve $5d_2 \equiv 1 \pmod{192}$
     • $5 \cdot 77 = 385 \equiv 1 \pmod{192}$ (because $385 - 2\cdot192 = 1$)
     • So $d_2 = 77$

   So Key B is:

   • Public: $(n_2, e_2) = (221, 5)$
   • Private: $(n_2, d_2) = (221, 77)$

   Comparison and conclusion

   • Which key has larger $n$?
     • $n_1 = 77$, $n_2 = 221$ → Key B has the larger modulus.
   • Which is harder to break (in principle)?
     • Key B, because factoring $221$ is (slightly) harder than factoring $77$, and in real RSA, larger $n$ means more security.
   • Why?
     • Security in RSA mainly depends on how hard it is to factor $n$.
     • A larger $n$ built from larger primes is more resistant to factorisation, so Key B is the stronger of the two (even though both are tiny and insecure in practice).

8. Spot the Weak Key

   Here are three possible RSA public keys:

   1. $(n = 91, e = 5)$
   2. $(n = 143, e = 7)$
   3. $(n = 221, e = 11)$

   Tasks:

   • Factor each $n$
   • Decide which one is the weakest and explain why
   • Decide which one is the strongest and explain why

   Solution

   Given public keys:

   1. $(n = 91, e = 5)$
   2. $(n = 143, e = 7)$
   3. $(n = 221, e = 11)$

   Factor each $n$:

   • $91 = 7 \cdot 13$
   • $143 = 11 \cdot 13$
   • $221 = 13 \cdot 17$

   All are small and easy to factor, but:

   • Weakest: $n = 91$ (smallest $n$)
   • Strongest (relatively): $n = 221$ (largest $n$)

   The reasoning: larger $n$ → harder (in principle) to factor.

9. Experiment With Encryption Collisions

   Pick two different messages $m_1$ and $m_2$ less than $n$.

   Encrypt both:

   • $c_1 \equiv m_1^e \pmod{n}$
   • $c_2 \equiv m_2^e \pmod{n}$

   Check whether $c_1 = c_2$.

   If they match, explain why that’s a problem.
   If they don’t, explain why RSA is designed to avoid collisions.

   Solution

   Recall what you did in the exercise:

   • You picked two different messages $m_1$ and $m_2$ with $1 \le m_1, m_2 < n$ and $m_1 \ne m_2$.
   • You encrypted them using the same RSA public key $(n, e)$: $$c_1 \equiv m_1^e \pmod{n}, \qquad c_2 \equiv m_2^e \pmod{n}.$$
   • You checked whether $c_1 = c_2$ (a collision) or $c_1 \ne c_2$.

   Let’s unpack what this means and why collisions are such a big deal.

   What would a collision mean?

   A collision would be a pair of different messages $m_1 \ne m_2$ such that: $$m_1^e \equiv m_2^e \pmod{n}.$$ Rewriting: $$m_1^e \equiv m_2^e \pmod{n} \quad \Longrightarrow \quad (m_1^e - m_2^e) \equiv 0 \pmod{n}.$$ Factor the left-hand side: $$m_1^e - m_2^e = (m_1 - m_2) \cdot x.$$ So if $n$ divides $m_1^e - m_2^e$, then $n$ divides the product $(m_1 - m_2)\cdot x$.

   If $m_1 \ne m_2$, then $m_1 - m_2$ is not $0$, so this would mean that $n$ shares a non-trivial factor with that $x$ term. In practice, for properly chosen RSA parameters and messages in the right range, this kind of collision is not expected to happen.

   Why RSA is designed to avoid collisions

   In “ideal” RSA (ignoring padding and practical details), we usually restrict to messages $m$ that are:

   • In the range $1 \le m < n$, and
   • Often also coprime to $n$ (so that $m$ has a multiplicative inverse modulo $n$).

   On the set of numbers that are coprime to $n$, the map $$m \mapsto m^e \pmod{n}$$ is a permutation when $e$ is chosen correctly (i.e. $\gcd(e, \varphi(n)) = 1$). That means:

   • It is one-to-one: different $m$ give different $c$.
   • It is onto: every possible ciphertext (in that reduced set) comes from some message.
   • It has an inverse map: $$c \mapsto c^d \pmod{n},$$ where $d$ is the private exponent.

   So, in this idealised setting, collisions should not occur: if $m_1 \ne m_2$, then $m_1^e \not\equiv m_2^e \pmod{n}$.

   What you likely observed in your experiment

   With a small RSA system (like $n = 77$, $e = 7$ or similar), and a couple of different messages $m_1, m_2$, you probably found:

   • $c_1 \ne c_2$.

   That is, no collision occurred in your test.

   This is exactly what we expect:

   • The encryption function behaves like a “scrambling” permutation on the allowed messages.
   • Each message has its own unique ciphertext (within that reduced set).

   Why a collision would be a serious problem

   If you did find $m_1 \ne m_2$ with $$m_1^e \equiv m_2^e \pmod{n},$$ then:

   • The encryption function would not be one-to-one.
   • Two different messages would become indistinguishable after encryption.
   • Decryption would be ambiguous: the same ciphertext could correspond to more than one message.

   In a real cryptographic system, that would be unacceptable:

   • You could not be sure which message was actually sent.
   • It would break the basic idea that encryption is a reversible transformation (given the private key).

   So, the absence of collisions is part of what makes RSA a sensible encryption scheme.